package week7.Chapter9_排序与查找;


import java.util.Scanner;

/**
 * 间隔排序法
 *
 * @author 唐才铭
 * @time2018-10-15 17:00
 * 20 17 23 19 20 18 09 28 11 04 29
 */
public class Gap_Sort {
    public static void Gap_Sort(int[] elements , int gap){
        int temp = 0;
        while(gap > 0)
        {
            for (int i = elements.length - 1; i >= 0; i--)
            {
                for (int j = 0; j <= i - 1; j++)
                {
                    if (gap > j)
                    {
                        if (elements[j]>elements[j+gap] )
                        {
                            temp = elements[j];
                            elements[j] = elements[j + gap];
                            elements[j + gap] = temp;
                            for (int element : elements){
                                System.out.print(element + "\t");
                            }
                            System.out.println();
                        }
                    }
                    else
                    {
                        if (elements[j]< elements[j-gap])
                        {
                            temp = elements[j];
                            elements[j] = elements[j - gap];
                            elements[j - gap] = temp;
                            for (int element : elements){
                                System.out.print(element + "\t");
                            }
                            System.out.println();
                        }
                    }

                }
            }
            gap--;
        }
//        int temp = 0;
//        while (gap > 0){
//            for (int i = elements.length;i>=0;i--){
//                for (int j = 0; j < i - 1; j++){
//                    if (gap > j){
//                        if (elements[j]>elements[j+i]){
//                            temp = elements[j];
//                            elements[j] = elements[j+i];
//                            elements[j+i] = temp;
//                        }
//                    }
//                    else
//                        if (elements[j]<elements[j-i]){
//                        temp = elements[j];
//                        elements[j] = elements[j-i];
//                        elements[j-i] = temp;
//                        }
//                }
//            }
//            gap--;
//        }
//        int position, scan;
//        int temp;
//
//        for (position = elementlength; position >= 1; position--){
//            for (scan = 0; scan <= position - 1; scan++){
//                if (elements[scan]>elements[scan+1] ){
//                    temp = elements[scan];
//                    elements[scan] = elements [scan + 1];
//                    elements[scan + 1] = temp;
//                }
//            }
//        }
//        if (gap>elements.length){
//            System.out.println("Gap Sort");
//        }
//        int temp = 0;
//        int size = elements.length;
//        for (int i = gap; i >= 1; i--){
//            for (int j = 0 ; j < size-i ; j++){
//                if (elements[j]>elements[j+1]){
//                    temp = elements[j];
//                    elements[j] = elements[j + i];
//                    elements[j + i] = temp;
//                }
//            }
//        }
//        while (gap >= 1){
//                for (int i = gap,j = 0 ; j < size-1-i;j++){
//                    if (elements[j]>elements[j + i + 1]){
//                        temp = elements[j];
//                        elements[j] = elements[j+i+1];
//                        elements[j + 1 + i] = temp;
//                    }
//                    for (int element : elements){
//                        System.out.print(element + "\t");
//                    }
//                    System.out.println();
////                    if (j+gap+1<size&&elements[j]>elements[j+gap+1]){
////                        temp = elements[j];
////                        elements[j] = elements[j+gap+1];
////                        elements[j+gap+1] = temp;
////                    }
////                    if (j+gap+1>size&&elements[j]>elements[size-gap]){
////                        temp = elements[j];
////                        elements[j]=elements[size-gap];
////                        elements[size-gap] = temp;
////                    }
//                }
//            gap = gap - newgap;
//        }

    }


    public static void main(String[] args) {
        System.out.println("Please enter an integer that needs to be sorted:  ");
        Scanner scanner = new Scanner(System.in);
        String[] temp_elements = scanner.nextLine().split(" ");
        int[] elements = new int[temp_elements.length];
        for (int i = 0 ; i<temp_elements.length;i++){
            elements[i] = Integer.parseInt(temp_elements[i]);
        }
        Gap_Sort(elements,3);
        System.out.println("The sorted integer is:  ");
        for (int element : elements){
            System.out.print(element + "\t");
        }
    }
}
